//91 Decode Ways
/*
已知字母 A-Z 可以表示成数字 1-26。给定一个数字串，求有多少种不同的字符串等价于这个
数字串

输入输出样例
	输入是一个由数字组成的字符串，输出是满足条件的解码方式总数

Input: "226"
Output: 3
有三种解码方式： BZ(2 26)、 VF(22 6) 或 BBF(2 2 6)

*/
int numDecodings(string s)
{
	int n = s.length();
	if (n == 0)
		return 0;
	int prev = s[0] - '0';
	if (!prev)
		return 0;
	if (n == 1)
		return 1;
	vector<int> dp(n + 1, 1);
	for (int i = 2; i <= n; ++i)
	{
		int cur = s[i - 1] - '0';
		if ((prev == 0 || prev > 2) && cur == 0)
		{
			return 0;
		}
		if ((prev < 2 && prev > 0) || prev == 2 && cur < 7)
		{
			if (cur)
			{
				dp[i] = dp[i - 2] + dp[i - 1];
			}
			else
			{
				dp[i] = dp[i - 2];
			}
		}
		else
		{
			dp[i] = dp[i - 1];
		}
		prev = cur;
	}
	return dp[n];
}